11  Collaborative Filtering

L’idea di base di questi sistemi è che se utenti condividevano gli stessi interessi nel passato, allora avranno verosimilmente gusti simili nel futuro. Questa tecnica è chiamata collaborative filtering perchè si filtrano gli item che potrebbero essere interessanti per un utente e perchè gli utenti implicitamente collaborano tra loro.

Approcci puri di CF non richiedono quindi alcuna conoscenza sugli item stessi. Il vantaggio di questa strategia è che non vi sono quindi dati da aggiungere e mantenere sugli item, anche se sfruttare le caratteristiche degli item potrebbe rendere le raccomandazioni più accurate.

L’idea è di prendere una matrice utenti-ratings come input e produrre come output una predizione numerica che indica quanto un certo item possa essere apprezzato o meno dall’utente attivo, oppure una lista di n items raccomandati.

11.1 User to User Collaborative Filtering

Dato un database di ranking e l’ID dell’utente attivo come input, dobbiamo identificare gli utenti neighbor che hanno avuto preferenze simili all’utente attivo nel passato. Quindi per ogni prodotto p che l’utente attivo non ha ancora visto, si produce una predizione sul gradimento.

Le assunzioni che vengono fatte sono 2: - Utenti con gusti simili in passato avranno gusti simili in futuro - Le preferenze di un utente rimangono stabili e consistenti nel tempo

Per misurare la similarità tra gli utenti possiamo utilizzare il coefficiente di Pearson: sim(a, b) = \dfrac{\displaystyle \sum_{p \in P} (r_{a, p} - \overline{r_a})(r_{b , p} - \overline{r_b})}{\sqrt{\displaystyle \sum_{p \in P} (r_{a , p} - \overline{r_a})^2} \sqrt{\displaystyle \sum_{p \in P} (r_{b , p} - \overline{r_b})^2}} - r_{a, p} è il rating dell’utente a per l’item p - P è il set di item valutati sia da a che da b - \overline{r_a} e \overline{r_b} è la media dei voti dati da a e b, questo per tenere conto del diverso stile di valutazione di ogni utente. Alcuni utenti tendono a dare voti molto alti, quindi un loro voto molto basso deve avere un peso maggiore rispetto a un voto basso dato da un utente restio a dare valutazioni alte - -1 \leq sim(a, b) \leq 1 con Pearson

In alternativa a Pearson si può utilizzare la similarità del coseno oppure il prodotto interno, o qualsiasi altra misura di similarità

A questo punto, dobbiamo decidere quali neighbor considerare e quanto forti devono essere le loro opinioni. Una funzione di predizione dell’oggetto p per l’utente a potrebbe essere quindi: pred(a, p) = \overline{r_a} + \dfrac{\displaystyle \sum_{b \in N} sim(a, b) \cdot (r_{b, p} - \overline{r_b})}{\displaystyle \sum_{b \in N} sim(a, b)}

  • N è il set di neighbor scelto. Per non rendere ancora più pesante la computazione, si sceglie un numero fisso di neighbor, in modo da bilanciare l’aspetto collaborativo e la similarità tra utenti. Scegliere un numero contenuto di neighbor in base alla similarità renderà le predizioni più precise.

11.1.1 Migliorare le metriche e la funzione di predizione

Per migliorare ulteriormente la funzione di predizione si posso effettuare alcune precisazioni: - Assegnare un peso diverso agli utenti vicini a seconda del numero di item correlati, ad esempio il peso della similarità di un utente potrebbe essere penalizzata per un fattore proporzionale al numero di item valutati in comune se questo numero è minore di un certo parametro \gamma > 0: w^{'}_{uv} = \dfrac{min\{|I_{uv}|, \gamma\}}{\gamma} \cdot w_{uv} - Assegnare un peso maggiore agli item con varianza maggiore, ovvero quelli per cui gli utenti sono più in disaccordo, riducendo l’importanza relativa dei gradimenti su items che piacciono a tutti gli utenti. Questo può essere fatto con l’Inverse User Frequency, una misura simile all’IDF. Viene dato un peso a ogni item in proporzione al logaritmo del rapporto degli utenti che hanno dato un rating per quell’item: \lambda_i = log \dfrac{U}{U_i}, dove i è l’item, U gli utenti totali, U_i gli utenti che hanno dato rating per i. Questa misura viene aggiunta al coefficiente di correlazione di Pearson: sim(a, b) = \dfrac{\displaystyle \sum_{p \in P} \lambda_p (r_{a, p} - \overline{r_a})(r_{b , p} - \overline{r_b})}{\sqrt{\displaystyle \sum_{p \in P} \lambda_p (r_{a , p} - \overline{r_a})^2} \sqrt{\displaystyle \sum_{p \in P} \lambda_p (r_{b , p} - \overline{r_b})^2}}

11.2 Item to Item Collaborative Filtering

La necessità di scansionare un numero vasto di potenziali neighbor rende impossibile calcolare le predizioni in tempo reale con lo User to User. In particolare lo user-based CF è un modello memory-based.

In alternativa, si utilizza un modello model-based, basato su un preprocessing offline, come l’item-based CF. A run-time, il modello allenato offline verrà usato per fare predizioni. L’idea principale è quella di calcolare le predizioni usando le similarità tra items e non tra utenti.

Per trovare oggetti simili potremmo usare la similarità del coseno, ma questa non tiene conto delle differenze nel comportamento degli utenti nel dare i rating. Questo viene risolto considerando una adjusted cosine similarity, che sottrae la media dei voti dell’utente dai ratings. Il range di questa nuova misura diventa [-1, +1] come il coefficiente di Person.

Quindi sia U il set di utenti che hanno dato un rating ad a e b, l’adjusted cosine similarity sarà calcolata come:

sim(a, b) = \dfrac{\displaystyle \sum_{ u \in U} (r_{u, a} - \overline{r_u}) (r_{u, b} - \overline{r_u})}{\sqrt{\displaystyle \sum_{u \in U} (r_{u, a} - \overline{r_u})^2} \sqrt{\displaystyle \sum_{u \in U} (r_{u, b} - \overline{r_u})^2}}

A questo punto, la predizione del rating per l’utente u del prodotto p sarà così fatta: pred(u, p) = \dfrac{\displaystyle \sum_{i \in ratedItems(u)} sim(i, p) \cdot r_{u, i}}{\displaystyle \sum_{i \in ratedItems(u)} sim(i, p)}

È bene precisare che, per vicini si intendono tutti quegli item: - simili per la metrica stabilita - per cui l’utente abbia espresso una valutazione.

Infatti, trovare un item simile a quello in esame, ma che non sia stato già valutato dall’utente non fornisce alcuna informazione. Stessa cosa per il modello user to user in cui vanno considerati solo quei vicini che abbiano espresso un giudizio per l’item considerato.

11.3 Rating espliciti e impliciti

Chiedere un rating espliciti per degli item all’utente è il modo più affidabile per raccogliere le opinioni degli utenti. La scala di rating da usare dipende dal dominio, si è notato ad esempio che nel dominio dei film una scala a 10 valori funziona meglio di una scala a 5 valori. Il problema principale con i rating espliciti è che questi richiedono un effort da parte dell’utente, che dal canto suo spesso non è intenzionato a lasciare dei rating. Questo porta ad avere pochi rating e quindi raccomandazioni mediocri.

In alternativa si può prevedere la raccolta di rating impliciti, usando click, visualizzazioni delle pagine, o altre metriche arbitrarie, ma che andranno interpretate nella maniera più corretta possibile, d’altro canto però non richiedono effort all’utente.

11.4 Problemi dei Collaborative Filtering RS

  • Matrice sparsa per i rating: il problema della sparsità è comune alla maggior parte dei recommender system perchè solitamente gli utenti valutano solo una piccola parte degli item disponibili. Ciò è aggravato dal fatto che gli utenti e gli item appena aggiunti al sistema non avranno alcuna valutazione (cold-start). Quando la matrice è sparsa, due utenti o item raramente hanno valutazioni in comune e gli approcci neighborhood-based prediranno le valutazioni usando dei set di vicini molto piccoli. Questo porterà a delle raccomandazioni non affidabili.
  • Cold-start: In un recommender system di tipo collaborativo, senza community non c’è modo di raccomandare item e si devono utilizzare approcci differenti (es: content-based o raccomandare oggetti popolari, forzare utenti a valutare item, default voting).
    • New-user: un nuovo utente non può avere alcuna raccomandazione con questo approccio fino a quando non esprime almeno una preferenza. Se non esprime delle preferenze, non può essere “vicino” di alcun altro utente. Un modo per risolvere questo problema può essere quello di sfruttare informazioni aggiuntive riguardo al profilo utente o di chiedere il rating di item del catalogo per tarare le sue preferenza.
    • New-item: un nuovo item non ha alcuna preferenza espressa da alcun utente. Quindi non risulterà neighbor di nessun altro oggetto nel caso item-to-item. Anche nel caso user-to-user sarà impossibile effettuare predizioni per alcun utente su quell’item perchè nessun’altro utente risulterà neighbor dell’utente su cui vogliamo calcolare la predizione. Un new-item non verrà raccomandato fino a quando non ci sarà qualche utente che lo valuterà.
  • Gray-sheep: un utente le cui opinioni sono neutre per la maggior parte degli item che ha valutato. Ciò rende impossibile trovare un set significativo di neighbors e quindi di effettuare raccomandazioni specifiche.
  • Canto delle sirene: valutazioni false o organizzate alterano lo stato del sistema e influenzano le raccomandazioni. Si possono creare profili fake o arruolare utenti per cercare di aumentare la valutazione complessiva di uno o più prodotti e diminuire quella dei competitors. Lo scopo di questo attacco è manipolare l’opinione della comunità attaccata, promuovendo o contrastando la diffusione di un prodotto. E’ possibile contrastare questi attacchi tramite l’analisi dei comportamenti degli utenti: nel caso di fake si avranno evidenti variazioni dalla media delle valutazioni degli items. Altre contromisure sono l’uso di captcha o altri metodi di inserimento manuale, che però non funzionano in caso di arruolamento di utenti dietro compenso.
  • I sistemi collaborativi sono delle black boxes, dato che l’unica spiegazione per la raccomandazione di un item è che utenti sconosciuti con gusti simili apprezzano quell’item
  • Scalabilità: sistemi di collaborative filtering richiedono molte risorse computazionali man mano che il numero di utenti e item aumenta

11.5 Valutare l’accuratezza delle predizioni

L’accuratezza consiste nel suggerire item realmente rilevanti per l’utente. La valutazione dell’accuratezza è un aspetto della valutazione offline di un recommender systems e consiste nel confrontare le raccomandazioni predette dal sistema con un insieme di giudizi di gradimento già espressi dagli utenti, detto ground truth.
Suddivido tale insieme di rating in training set e test set, usati per addestrare e testare il recommender system.
Il confronto fra predizioni e giudizi reali si effettua usando metriche di:
- MAE (Mean Absolute Error): calcola la deviazione tra i rating predetti e i rating reali: \dfrac{1}{n} \displaystyle \sum_{i = 1}^n |p_i- r_i| - RMSE (Root Mean Square Error): come MAE ma penalizza deviazioni più grandi utilizzando il quadrato della differenza tra rating predetto e rating attuale. \sqrt{\dfrac{1}{n} \displaystyle \sum_{i = 1}^n (p_i- r_i)^2}